#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
Introduction to Programming in Java - An Interdisciplinary Approach

All book programs ported to Python by
Scott C. King (revisionx at {gee}ma1l <dot> c0m).

All program examples pass Pylint with a perfect 10.00 score.
Pylint:  http://www.pylint.org/


Program 1.6.2 - Simulating a random surfer

Syntax:
python transition.py < tiny.txt | python randomsurfer.py 10000
tiny.txt is a required file (supplied)


Notes:
int(sys.argv[1]) == Integer.parseInt(args[0])

sys is a required import here in order to use stdin.
https://docs.python.org/2/tutorial/stdlib.html

Division updated in PEP 238 is better suited for this task, which is
imported using the __future__ module.

https://www.python.org/dev/peps/pep-0238
https://docs.python.org/2.7/library/__future__.html

'''

from __future__ import division
import sys
import random


def main():
    ''' input transition matrix, output behavior (page frequencies) by
        simulating random-surfer leaps and links '''

    moves = int(sys.argv[1])
    pages = int((sys.stdin.readline().strip().split())[0])

    # Read transition matrix
    trans_matrix = [[0 for _ in range(pages)] for _ in range(pages)]

    for row in range(pages):
        line = sys.stdin.readline().strip().split()
        for col in range(pages):
            trans_matrix[row][col] = float(line[col])

    current_page = 0    # start at page 0
    frequency = [0] * pages

    for _ in range(moves):
        total = 0.0
        rand_val = random.random()
        page = 0        
        for page in range(pages):
            # find interval containing random value
            total += trans_matrix[current_page][page]
            if rand_val < total:
                current_page = page
                break
        frequency[page] += 1

    for freq in frequency:
        print '{:8.5f}'.format(float(freq) / moves),
    print


if __name__ == '__main__':
    main()
